package 二叉树;


/**
 * https://leetcode.cn/problems/path-sum-iii/description/?envType=study-plan-v2&envId=top-100-liked
 */
public class _437_路径总和III {

    public int pathSum(TreeNode root, int targetSum) {
        if (root == null) return 0;
        return dfs(root, targetSum) + pathSum(root.left, targetSum) + pathSum(root.right, targetSum);
    }


    private int dfs(TreeNode root, int targetSum) {
        if (root == null) return 0;

        return (root.val == targetSum ? 1 : 0) + dfs(root.left, targetSum - root.val) + dfs(root.right, targetSum - root.val);
    }
}
